A bounding volume hierarchy (BVH) may improve ray tracing algorithms. A BVH is a tree of bounding volumes enclosing objects within a scene. Ray tracing generates images by tracing paths of light rays through a virtual three-dimensional environment. Instead of checking ray traversal for each of a large number of objects, ray traversal may be more easily checked for a volume (“parent node”) in a BVH that bounds those objects. If so, then successively smaller bounding volumes (“sibling nodes”) can be tested for ray intersection.
In reduced precision bounding volume hierarchies, a local low resolution grid is selected such that the origin of the grid is aligned with a parent u axis and the dimensions of the grid are selected to be the smallest value that is a power of two and greater than the dimensions of the parent bounding box. The bounding box is quantized by computing integer offsets of the bounding box coordinates in the local grid.
A BVH with bounding volumes may be represented by axis-aligned bounding boxes that are specified using its minimum coordinate p and maximum coordinate q, where (p, q)ε3 These coordinates can be compressed by quantizing them to a local low resolution grid and decompressed as the BVH is traversed to evaluate ray-scene intersections. In the following, the components of a point p are accessed as p=(p0, p1, p2).
Let (uparent, vparent) be the corresponding coordinates of the quantized bounding box. The next step is to encode children box inside the parent. Since the BVH compression is lossy, the decompressed coordinates can be different from the unquantized coordinates. The local low resolution grid is selected such that the origin of the grid is aligned with uparent and the dimensions of the grid are selected to be the smallest value that is a power of two and greater than the parent bounding box. The quantized bounding box is derived by computing relative offsets of the bounding box coordinates to the origin of the grid and quantizing the result to a small number of bits, Nb. For an axis i, these operations are described by:
                                          r            i                    =                      ⌊                                                            (                                                            p                      i                                        -                                          u                      i                      parent                                                        )                                                  2                  i                                      e                    parent                                                              ⁢                              2                                  (                                      N                    b                                    )                                                      ⌋                          ,                              s            i                    =                      ⌊                                                            (                                                            q                      i                                        -                                          u                      i                      parent                                                        )                                                  2                  i                                      e                    parent                                                              ⁢                              2                                  (                                      N                    b                                    )                                                      ⌋                                              (        1        )            where 2eparenti is the grid dimension along x and (r, s)εZ3>0 are the quantized offsets relative to the quantized parent bounding box. Using floor rounding mode guarantees that (ri, si)ε[0, 2Nb, −1]. The exponent eiparent is given by:eiparent=argkmin(2k>(viparent−uiparent))  (2)
The bounding boxes can be iteratively decompressed from the quantized coordinates when the BVH is traversed from the root node as described in Equations 3 and 4:ui=uiparent+ri2(eiparent−Nb)  (3)vi=uiparent+(si+1)2(eiparent−Nb),  (4)where (u, v) are the decomposed coordinates that are initialized with the full precision coordinates of the root node at the start of the traversal. The value of si is incremented by one, which compensates for the negative error introduced by the rightmost floor operation in Equation 1. This also guarantees vi−ui>0, which is required for deterministic grid dimensions if a parent node is decompressed from a child node.
Intersections between rays and the compressed BVH can be determined by traversing the BVH, decompressing the node bounding boxes and computing ray-bounding box intersections, which can be evaluated using Kay and Kajiya's slab test. This test computes three distance intervals along the ray to pairs of planes called slabs which define faces of the bounding box. The slab test uses a parameterized ray representation o+td, where o is the ray origin, d is the ray direction and t is the parametric distance along the ray. A pair of parametric distances is computed along each axis i:λi=(ui−oi)wi  (5)μi=(vi−oi)wi  (6)where
      w    i    =      1    d  is the ray slope. Parametric distances corresponding to the y and z axes can be computed similarly. Assuming the slopes (wx, wy, wz) are positive, a ray intersects the bounding box if,max(λmax,tmin)≦min(μmin+2ulp(μmin,tmax)  (7)
where λmax and tmin are the maximum and minimum values of λi and μi respectively and (tmin, tmax) represent the clip distances of the ray. The function ulp( ) returns the unit in the last place of a finite precision floating-point value. Adding this compensation term umin guarantees watertight intersection results. If a slope wi is negative, the corresponding values of λi and μi have to be swapped.
The slab tests can be performed with reduced precision arithmetic if the origin of the ray is moved closer to the bounding box after each traversal step. This can be done by updating the origin of the ray after each traversal step. However, if the ray origin is modified, the values of (λ, μ) computed for the parent node cannot be reused for the child nodes. Therefore, for a pair of sibling nodes, Equations 5 and 6 have to evaluated for each of the twelve bounding planes, doubling the number of computations.